#include <iostream>
#include <vector>
#include <queue>
using namespace std;
/**
 * @brief
 * m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], newColor < 216
0 <= sr < m
0 <= sc < n
 *
 */
class Solution
{
public:
   //深度优先搜索
   void dfs(vector<vector<int>> &image, int x, int y, int color, int newColor)
   {
      const int dx[4] = {1, 0, 0, -1};
      const int dy[4] = {0, 1, -1, 0};
      if (image[x][y] == color)
      {
         image[x][y] = newColor;
         for (int i = 0; i < 4; i++)
         {
            int mx = x + dx[i], my = y + dy[i];
            if (mx >= 0 && mx < image.size() && my >= 0 && my < image[0].size() && image[mx][my] == color)
            {
               dfs(image, mx, my, color, newColor);
            }
         }
      }
   }
   vector<vector<int>> floodFill(vector<vector<int>> &image, int sr, int sc, int newColor)
   {
      int color = image[sr][sc];
      if (color != newColor)
      {
         dfs(image, sr, sc, color, newColor);
      }
      return image;
   }

   /**
    * @brief BFS
    *
    * @param image
    * @param sr
    * @param sc
    * @param newColor
    * @return vector<vector<int>>
    */
   vector<vector<int>> floodFill_2(vector<vector<int>> &image, int sr, int sc, int newColor)
   {
      const int dx[4] = {1, 0, 0, -1};
      const int dy[4] = {0, 1, -1, 0};
      int curColor = image[sr][sc];
      if (newColor == curColor)
      {
         return image;
      }
      int n = image.size();
      int m = image[0].size();
      queue<pair<int, int>> que;
      que.emplace(sr, sc);
      image[sr][sc] = newColor;
      while (!que.empty())
      {
         int x = que.front().first, y = que.front().second;
         que.pop();
         for (int i = 0; i < 4; i++)
         {
            int mx = x + dx[i], my = y + dy[i];
            if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == curColor)
            {
               image[mx][my] = newColor;
               que.emplace(mx, my);
            }
         }
      }
      return image;
   }
};
int main()
{

   system("pause");
   return 0;
}
